package com.github.hgkmail.hello.leetcode101.collection.array;

import java.util.ArrayList;
import java.util.List;

//限定了空间复杂度是常量，因此用题目给的数组记录信息，比如使用正负号
//正数：出现0次或2次
//负数：出现1次（关注这个）
public class LC442FindAllDuplicatesInAnArray {
    public List<Integer> findDuplicates(int[] nums) {
        //base
        int n=nums.length;
        if (n<=0) {
            return new ArrayList<>();
        }
        int pos;
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            pos = Math.abs(nums[i])-1;
            if (nums[pos]<0) { //nums[i]已经出现过1次了
                res.add(Math.abs(nums[i]));
            } else { //未出现过
                nums[pos]*=-1;
            }
        }

        return res;
    }

    public static void main(String[] args) {
        System.out.println(new LC442FindAllDuplicatesInAnArray().findDuplicates(new int[]{4,3,2,7,8,2,3,1}));
    }
}
